Hidden Markov Model-based optical character recognition (OCR) may need to evaluate a large number of hypotheses, represented by paths through states of the Hidden Markov Model, at the boundaries between characters. An optical character recognition system using a Hidden Markov Model may solve both character segmentation, locating the boundaries between characters in input images of text, and classification, predicting labels for the characters segmented from the input image, at the same time. This may result in the OCR system attempting to evaluate and classify all possible characters that the Hidden Markov Model has been trained to recognize at each character boundary, or segmentation point. The computational cost of performing OCR may be increased by the large number of fan-out connections at a character boundary, which may make the decoding time unacceptably long, especially for languages which have a large number of characters.
Hidden Markov Model-based automated speech recognition (ASR) may operate similarly to Hidden Markov Model-based OCR, with segmentation points and boundaries between words. Both ASR and OCR systems may use time-synchronous Viterbi decoding to decode input using a Hidden Markov Model. In spoken language, sounds may be dependent on surrounding sounds. This may allow ASR systems to use context dependent models to form acoustic models and a trie-based structure which shares prefixes of words to form a decoding network, resulting in a reduction in the number of words an ASR system has to evaluate at word boundaries, decreasing the fan-out. In written language, all characters may be connected to all other characters, so OCR systems may use optical models and a linear structure which does not share any prefixes among characters to form a decoding network. OCR systems may not be able to reduce the number of characters considered at a predicted segmentation point in the same manner as an ASR system. Standard beam pruning algorithms may be used with OCR systems, but the decoding speed may still be too slow because of the fan-out at character boundaries.